/**
 * @a https://leetcode.cn/problems/jump-game-ii/description/
 */

#include "../common.h"

// dp
class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n,10e4+4);
        dp[0] = 0;

        for(int i = 0; i < n; ++i){
            for(int j = 0; j + i < n && j <= nums[i]; ++j){
                dp[i + j] = min(dp[i + j], dp[i] + 1);
            }
        }
        return dp[n - 1];
    }
};

// 贪心
class Solution {
public:
    int jump(vector<int>& nums) {
        int step = 0;
        int cur_end = 0;
        int farest_end = 0;
        for(int i = 0; i < nums.size() - 1; ++i){
            farest_end = max(i + nums[i], farest_end);
            if(cur_end == i){
                ++step;
                cur_end = farest_end;
            }
        }
        return step;
    }
};


class Solution {
public:
    int jump(vector<int>& nums) {
          
    }
};